MAYBE 117.402 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could not be shown:



HASKELL
  ↳ BR

mainModule Main
  ((enumFromTo :: Float  ->  Float  ->  [Float]) :: Float  ->  Float  ->  [Float])

module Main where
  import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL
  ↳ BR
HASKELL
      ↳ COR

mainModule Main
  ((enumFromTo :: Float  ->  Float  ->  [Float]) :: Float  ->  Float  ->  [Float])

module Main where
  import qualified Prelude



Cond Reductions:
The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False

The following Function with conditions
takeWhile p [] = []
takeWhile p (x : xs)
 | p x
 = x : takeWhile p xs
 | otherwise
 = []

is transformed to
takeWhile p [] = takeWhile3 p []
takeWhile p (x : xs) = takeWhile2 p (x : xs)

takeWhile1 p x xs True = x : takeWhile p xs
takeWhile1 p x xs False = takeWhile0 p x xs otherwise

takeWhile0 p x xs True = []

takeWhile2 p (x : xs) = takeWhile1 p x xs (p x)

takeWhile3 p [] = []
takeWhile3 vz wu = takeWhile2 vz wu



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
HASKELL
          ↳ NumRed

mainModule Main
  ((enumFromTo :: Float  ->  Float  ->  [Float]) :: Float  ->  Float  ->  [Float])

module Main where
  import qualified Prelude



Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.

↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
HASKELL
              ↳ Narrow
              ↳ Narrow

mainModule Main
  (enumFromTo :: Float  ->  Float  ->  [Float])

module Main where
  import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_not(Succ(wv191200), Succ(wv194700)) → new_not(wv191200, wv194700)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_primPlusNat(Succ(wv191800), Succ(wv189400)) → new_primPlusNat(wv191800, wv189400)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_primMulNat(Succ(wv3000), wv18940) → new_primMulNat(wv3000, wv18940)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_not0(wv300, Succ(wv18950), Succ(wv4000), wv31, wv41) → new_not0(wv300, wv18950, wv4000, wv31, wv41)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_not1(wv300, Succ(wv18940), Succ(wv4000), wv31, wv41) → new_not1(wv300, wv18940, wv4000, wv31, wv41)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ MNOCProof
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))

The TRS R consists of the following rules:

new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)

The set Q consists of the following terms:

new_ps(Neg(Succ(Zero)))
new_sr(Neg(x0))
new_ps(Neg(Succ(Succ(x0))))
new_ps(Pos(x0))
new_primPlusNat1(Zero, x0)
new_primMulNat0(Succ(x0), x1)
new_primPlusNat0(Succ(x0), Zero)
new_primMulNat1(Succ(x0))
new_sr(Pos(x0))
new_primMulNat0(Zero, x0)
new_primPlusNat0(Zero, Zero)
new_primPlusNat0(Succ(x0), Succ(x1))
new_primPlusNat1(Succ(x0), x1)
new_ps(Neg(Zero))
new_primPlusNat2(x0)
new_primMulNat1(Zero)
new_primPlusNat0(Zero, Succ(x0))

We have to consider all minimal (P,Q,R)-chains.
We use the modular non-overlap check [17] to decrease Q to the empty set.

↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ NumRed
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
                    ↳ MNOCProof
QDP
                        ↳ NonTerminationProof
              ↳ Narrow

Q DP problem:
The TRS P consists of the following rules:

new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))

The TRS R consists of the following rules:

new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)

Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))

The TRS R consists of the following rules:

new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)


s = new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) evaluates to t =new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:




Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) to new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843)).




Haskell To QDPs